//035. 圆形素数
//        数字 197 是一个圆形素数，这是因为所有它各位数的轮换 197，971 以及 719 也都是素数。
//        一百以下总共有十三个这样的素数，包括：2，3，5，7，11，13，17，31，37，71，73，79
//        和 97。求一百万以下有多少个这样的圆形素数？
//        答案：55


public class Week035 {
    /*
     *@ prime[i] :第i+1个素数
     *@ mv[i]    :i的最小质因子
     *@ 质数的最小质因子为它本身
     *@ 请不要更改传入的数组的值（即全为0）
     */
    // 欧拉筛1~n的素数
    public static int getPrime(int[] prime, int[] mv, int n) {
        int tot = 0;
        for (int i = 2; i <= n; ++i) {
            if (mv[i] == 0) {
                prime[tot++] = i;
                mv[i] = i;
            }
            for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
                mv[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
        return tot;
    }

    static void reverse(int[] list, int cnt) {
        for (int i = 0, end = cnt >> 1; i < end; ++i) {
            int t = list[i];
            list[i] = list[cnt - i - 1];
            list[cnt - i - 1] = t;
        }
    }

    static void run() {
        final int N = 1000000;
        int[] primes = new int[N >> 1];
        int[] mv = new int[N];
        int tot = getPrime(primes, mv, N - 1);
        int[] list = new int[6];
        int ans = 0;
        for (int i = 0; i < tot; ++i) {
            int cnt = 0;
            for (int j = primes[i]; j != 0; j /= 10) list[cnt++] = j % 10;
            reverse(list, cnt);
            //最多轮换cnt-1次
            boolean yes = true;
            for (int j = 1; yes && j < cnt; ++j) {
                int next = 0;
                //轮换的后半部分数字
                for (int k = j; k < cnt; ++k) next = next * 10 + list[k];
                //轮换的前半部分数字
                for (int k = 0; k < j; ++k) next = next * 10 + list[k];
                if (mv[next] != next) yes = false;//如果不是质数
            }
            if (yes) ++ans;
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
